import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.Comparator;

public class test_24_08_26 {

    //双向循环链表 + 哨兵节点
    class CircularDoubleLinkedList {
        class Node {
            int date;
            Node next;
            Node prev;

            public Node(int date) {
                this.date = date;
                this.next = null;
                this.prev = null;
            }

            public Node(int date, Node next, Node prev) {
                this.date = date;
                this.next = next;
                this.prev = prev;
            }
        }

        Node Dummy;
        int size;

        public CircularDoubleLinkedList() {
            Dummy = new Node(0);
            Dummy.next = Dummy;
            Dummy.prev = Dummy;
            this.size = 0;
        }

        public void addFirst(int val) {
            Node addnode = new Node(val, Dummy.next, Dummy);
            Dummy.next.prev = addnode;
            Dummy.next = addnode;
            size++;
        }

        public void addLast(int val) {
            Node node = Dummy.prev;
            Node addnode = new Node(val,Dummy,node);
            node.next = addnode;
            Dummy.prev = addnode;
            size++;
        }

        public void removeFirst() {
            if(Dummy.next == null) return;
            Dummy.next.next.prev = Dummy;
            Dummy.next = Dummy.next.next;
            size--;
        }

        public void removeLast() {
            if(Dummy.next == null) return;
            Dummy.prev.prev.next = Dummy;
            Dummy.prev = Dummy.prev.prev;
            size--;
        }

        /**
         * remove：根据传入的val删除链表中==val的元素
         * 注意点：只会删除链表中第一个符合条件的元素
         * */
        public void remove(int val) {
            Node node = Dummy.next;
            for(int i = 0; i < size; i++) {
                if(node.date == val) {
                    Node prevnode = node.prev;
                    prevnode.next = node.next;
                    node.next.prev = prevnode;
                    return;//只删除第一个，否则删除多个
                }
                node = node.next;
            }
            size--;
        }
        public void printList() {
            Node node = Dummy.next;
            while(node != Dummy) {
                System.out.println(node.date);
                node = node.next;
            }
        }
    }




    public void main(String[] args) {
        CircularDoubleLinkedList linkedList = new CircularDoubleLinkedList();
        linkedList.addFirst(100);
        linkedList.addFirst(222);
        linkedList.addFirst(355);
        linkedList.addLast(10000);
        linkedList.removeFirst();
        linkedList.addFirst(32);
        linkedList.removeLast();
        linkedList.removeFirst();
        linkedList.remove(100);
        linkedList.printList();
        ArrayList<String> arr = new ArrayList<>();
        int size = arr.size();
        System.out.println();

        arr.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return 0;
            }
        });


    }

}


